package test.algorithm.sample ;

import java.util.BitSet ;

/**
 * BloomFilter：一个用于大数据去重的算法
 * @author 80002165 @date 2017年4月24日 上午9:06:54
 */
/*
 * 算法概述：有这样的需求，想做一个过滤器，过滤掉已有的内容，简单的说就是去重。那么可有的解决方案：
 * 1、存数据库或是redis等缓存服务器，每次从数据库取数据进行比较，看内容是否在数据库中，如果在，则过滤掉
 * 2、使用HashSet来保存每次的值。
 * 3、将需要保存的值进行MD5或SHA-1转换存到HashSet中
 * 4、将需要保存的值映射到BitSet中，将对应位设置为true
 * 每种方案都有缺点：1,2两种方案查询服务器，除了性能方面的考虑，还有安全方面的问题
 * 
 * bloomfilter的优缺点：
 * 不会漏掉黑名单中的任何一个值，但是也存在小概率会误过滤，将本不在过滤名单中的内容判定为在过滤名单中
 */

/*
 * BloomFilter各种值计算参考：
 * http://blog.csdn.net/jiaomeng/article/details/1495500
 */
public class BloomFilter {
    // 默认的列表长度
    private final static int DEFAULTSIZE = 1 << 24 ;
    // 初始化列表
    private static BitSet bitSet = new BitSet(DEFAULTSIZE) ;
    
    // 定义一个计算哈希值的种子数组
    private static int[] seeds = { 5, 7, 11, 13, 31, 37, 61 } ; 
    
    private static SimpleHash[] simpleHashs = new SimpleHash[seeds.length] ;
    
    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            simpleHashs[i] = new SimpleHash(seeds[i], DEFAULTSIZE) ;
        }
    }
    
    public void add(String value) {
        for (SimpleHash simpleHash : simpleHashs) {
            int bitIndex = simpleHash.hash(value) ;
            bitSet.set(bitIndex, true) ;
        }
    }
    
    public void delete(String value){
        for (SimpleHash simpleHash : simpleHashs) {
            int bitIndex = simpleHash.hash(value) ;
            bitSet.set(bitIndex, false) ;
        }
    }
    
    public boolean contain(String value) {
        if (value == null)
            return false ;
        
        boolean res = true ;
        for (SimpleHash simpleHash : simpleHashs) {
            int bitIndex = simpleHash.hash(value) ;
            /** 只有所有位上的数都是true则res最终的结果为true,只要有一个值不为true,则res一定是false即表示该内容不存在 */
            res = res && bitSet.get(bitIndex) ;
            if (!res)
                break ;
        }
        return res ;
    }
    
    // 定义一个计算值位置的对象
    static class SimpleHash {
        private int seed ;
        private int cap ;
        
        public SimpleHash(int seed, int cap) {
            this.seed = seed ;
            this.cap = cap ;
        }
        
        // 计算给定的参数的hash值，即对应bitset中的下标识
        public int hash(String value) {
            int result = 0 ;
            int len = value.length() ;
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i) ;
            }
            /** 确保hash值不会大于bitset的长度 */
            return (cap - 1) & result ;
        }
    }
    
    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter() ;
        System.out.println(bloomFilter.contain("fang") );
        bloomFilter.add("shu") ;
        System.out.println(bloomFilter.contain("shu") );
        bloomFilter.delete("shu");
        System.out.println(bloomFilter.contain("shu") );
    }
}
